package 链表;

/**
 * https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/
 * <p>
 * 输入两个链表，找出它们的第一个公共节点。
 */
public class 剑指_Offer_52_两个链表的第一个公共节点 {

    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(4, new ListNode(1, new ListNode(8, new ListNode(4, new ListNode(5, null)))));
        ListNode listNode2 = new ListNode(5, new ListNode(0, new ListNode(1, new ListNode(8, new ListNode(4, new ListNode(5, null))))));
        ListNode result = getIntersectionNode(listNode1, listNode2);
        System.out.println(result);
    }

    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        if (headA == headB) return headA;

        ListNode p1 = headA;
        ListNode p2 = headB;

        while (p1 != p2) {
            p1 = p1 == null ? headB : p1.next;
            p2 = p2 == null ? headA : p2.next;

            if (p1 == p2) return p1;
        }

        return null;
    }
}
